//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 👍 4217 👎 0

package leetcode.editor.cn;

public class _5_LongestPalindromicSubstring {
    public static void main(String[] args) {
        String str = "bb";
        Solution solution = new _5_LongestPalindromicSubstring().new Solution();
        String s = solution.longestPalindrome(str);
        System.out.println(s);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 动态规划
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
            if (s.length() < 2) {
                return s;
            }
            char[] charArray = s.toCharArray();
            int len = s.length();
            int start = 0;
            int maxLen = 1;

            boolean[][] bp = new boolean[len][len];
            for (int i = 0; i < len; i++) {
                bp[i][i] = true;
            }
            for(int j = 1; j < len; j++) {
                for(int i = 0; i < j; i++) {
                    if (charArray[i] != charArray[j]) {
                        bp[i][j] = false;
                    } else {
                        if (j - i + 1 - 2 < 2) {
                            bp[i][j] = true;
                        } else {
                            bp[i][j] = bp[i+1][j-1];
                        }
                    }

                    if (bp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
            return s.substring(start, start + maxLen);
        }

        /**
         * 中间扩散
         * @param s 字符串
         * @return  返回所求
         */
        public String longestPalindrome_2(String s) {
            if (s.length() < 2) {
                return s;
            }

            char[] charArray = s.toCharArray();

            int maxLen = 1;
            int start = 0;

            for (int i = 0; i < s.length() - 1; i++) {
                // 奇数odd
                int oddLen = expandAroundCenter(charArray, i, i);
                // 偶数even
                int evenLen = expandAroundCenter(charArray, i, i+1);
                int len = Math.max(oddLen, evenLen);
                if (len > maxLen) {
                    maxLen = len;
                    start = i - (len - 1) / 2;
                }
            }
            return s.substring(start, start + maxLen);
        }

        private int expandAroundCenter(char[] charArray, int left, int right) {
            while (left >= 0 && right < charArray.length) {
                if (charArray[left] != charArray[right]) {
                    break;
                } else {
                    left--;
                    right++;
                }
            }
            return right - left + 1 - 2;// 不包括两边
        }

        /**
         * 暴力解法
         * @param s
         * @return
         */
        public String longestPalindrome_1(String s) {
            if (s.length() < 2) {
                return s;
            }
            int len = 1;
            int start = 0;
            char[] charArray = s.toCharArray();

            for (int i = 0; i < s.length() - 1; i++) {
                for (int j = i + 1; j < s.length(); j++) {
                    if (j - i + 1 > len && validPalindromic(charArray, i, j)) {
                        len = j - i + 1;
                        start = i;
                    }
                }
            }

            return s.substring(start, start + len);
        }

        private boolean validPalindromic(char[] charArray, int left, int right) {
            while (left < right) {
                if (charArray[left] != charArray[right]) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

        /**
         * 自己的暴力解法，更暴力
         * @param s
         * @return
         */
        public String longestPalindrome_tooBig(String s) {
            int len = 0;
            String res = null;
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j <= s.length(); j++) {
                    StringBuilder sb = new StringBuilder();
                    for (int k = i; k < j; k++) {
                        sb.append(s.charAt(k));
                    }
                    boolean flag = true;
                    int length = sb.length();
                    for (int k = 0; k < length; k++) {
                        if (sb.charAt(k) != sb.charAt(length - k - 1)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag && length > len) {
                        len = length;
                        res = sb.toString();
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}